


	SORTARE - SOLUTIE
       -------------------

	Se construieste graful neorientat, in care varfuri sunt pozi-
tiile din permutare, si muchii perechile de pozitii intre care se pot
interschimba elemente.
	Se executa n pasi:
- la pasul i, se aduce pe pozitia i, elementul cu numarul i.
- se cauta un drum de la pozitia pe care se afla acesta la pozitia i;
- se deplaseaza acest element pana pe pozitia sa (toate celelalte ele-
mente se dau cate o pozitie inapoi - de pe drumul ales)
- se deplaseaza elementul aflat initial pe pozitia i, pe pozitia pe
care se afla elementul cu numarul i (toate celelalte elemente se dau
acum cu un pas inainte , adica revin pe pozitiile pe care erau -> s-au
interschimbat, de fapt, doar doua elemente, celelalte ramanand neschim-
bate!!).